Algorithms for encryption, respectively for decryption, or again for enciphering, are aimed at encrypting, respectively decrypting, data Such algorithms generally comprise a chaining together of several operations, or calculations, that are applied successively to a data item to be encrypted so as to obtain an encrypted data item. These algorithms use secret keys.
Such encryption algorithms may suffer from “attacks” which are aimed at violating the confidentiality of keys used. Numerous types of attacks are known today.
Thus, certain attacks are based on information leaks detected during the execution of the encryption algorithm. These attacks are generally founded on a correlation between the information leaks detected during the processing by the encryption algorithm of the data item and of the key or keys (attacks by analyzing the consumption of current, electromagnetic emanations, calculation time, etc).
Procedures for protecting against such attacks are known. One of the protection procedures commonly used is the random masking of the intermediate data manipulated by the encryption or decryption algorithm. In this type of protection, the input data are masked by random values. Thus, the intermediate data resulting from the operations performed in the algorithm may be decorrelated from the key or keys.
The attacks which are aimed at violating the confidentiality of the secret keys of an encryption algorithm are similar to the attacks aimed at violating the confidentiality of the secret keys of a decryption algorithm. In the following sections the characteristics described in relation to an encryption algorithm also relate to a decryption algorithm.
An encryption algorithm generally comprises several linear and/or nonlinear operations. For an initial data item to be encrypted, an intermediate data item is obtained after each of the operations of the encryption algorithm. When masked intermediate data are manipulated, a masked intermediate data item is obtained after each operation. The encryption algorithm is thus protected.
It is however useful to recover the unmasked intermediate data item after each of these operations by “demasking” the data item. It is easy to demask an intermediate data item resulting from a linear operation. Specifically, a linear operation L applied to a data item x masked by an exclusive or with a random mask m, may be written in the form:L(x⊕m)=L(x)⊕L(m).
Thus, knowing m, it is easy to demask L(x⊕m) to obtain L(x).
It is entirely otherwise fox nonlinear operations. Specifically, for a nonlinear operation F applied to a data item x masked by an exclusive or with a random mask m, it is generally possible to write:F(x⊕m)≠F(x)⊕F(m).
In order to demask an intermediate data item manipulated by the encryption algorithm, it is necessary to perform a series of calculations which may be complex and expensive depending on the encryption algorithm to be protected.
Encryption algorithms are known that use nonlinear operations, such as the DES (“data encryption standard”) algorithm or else the AES (“advanced encryption standard”) algorithm. Several methods of protection by masking of the AES algorithm have already been proposed.
In such algorithms, the nonlinear operations are generally implemented in the form of substitution tables. Thus, a nonlinear operation corresponding to a substitution table tab[i], applied to a data item x may be written in the following form:y=tab[x]. 
The protection by masking in this case requires the generation on the fly of the randomly masked tables. Thus, a masked nonlinear operation corresponding to a masked substitution table tab′[i], applied to a data item x masked by a random mask m1 may be written in the form:y′=tab′[x⊕m1]=y⊕m2
In order to be able to demask the data item y′ thus obtained, a solution consists in storing the masked tables. Protection procedures of this type are proposed for the DES encryption algorithm in the document by Louis Goubin and Jacques Patarin ‘DES and Differential Power Analysis—The “Duplication” Method’, in Cetin Kaya Koç and Christof Paar, editors, Proceedings of CHES '99, volume 1717 of ‘Lecture Notes in Computer Science’, pages 158-172, Springer-Verlag, 2000, as well as in patent FR 2802741 ‘Dispositif mettant en oeuvre un algorithme de chiffrage par bloc à répétition de rondes’ [device implementing a blockwise encryption algorithm with repetition of rounds].
However, such a solution may turn out to be extremely expensive in terms of memory room, in particular when the unmasked substitution table is of relatively large size.
For example, the nonlinear operation of the AES may be implemented using a substitution table having a size of 256 bytes. The simultaneous encryption of 16 bytes of a message requires the storage of 16 masked substitution tables each of 256 bytes. The memory size required to mask the nonlinear operation thus implemented is consequently 4 Kb.
A drawback of this type of protection is therefore that it requires a consequential memory size.
Also known is the document ‘Provably Secure Masking of AES’ by Johannes Blömer, Guarjardo Merchan, and Volker Krummel published on Apr. 30, 2004 and the document ‘Secure and Efficient Masking of AES—A Mission Impossible’ version 1 of E. Oswald, Stephan Mangard and Norbert Pramstaller dated from 4 Jun. 2004 which propose that the nonlinear operation of the AES algorithm be carried out in the finite field GF(4).
The latter article proposes a procedure for masking the operations of the AES algorithm in which the nonlinear operation of an intermediate masked data item is transformed into a linear operation by transposition from one finite field (GF(28)) to another (GF(4)).
However, such a method of masking of the AES proposes that the nonlinear operations be carried out in GF(4) and hence that bits be manipulated 2 by 2.
In general, it is easier to efficaciously implement operations carried out on blocks of bits of size substantially equal to the number of bits processed simultaneously by the microprocessor used rather than operations carried out on blocks of bits of size very substantially different from the number of bits processed simultaneously by the microprocessor.
Thus, an efficacious implementation of an encryption algorithm manipulating bits 2 by 2 is not easy on 8, 16, 32 or even 64-bit microprocessors.